package Tree;

import java.util.HashMap;

/**
 *  题目：向下的路径节点值之和bxcvbxcvfg3
 *  题目详解 ：
 *  给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *  路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 */
public class PathSum {
    /**
     *  核心思想 ：
     *  （1）由于我们并不知道具体是哪条路径和目标路径相吻合，所以需要去进行搜索；
     *  （2）需要去将此路径上的所有可能值，都保存在hash表中；
     *  （3）当满足 目标长度 = （当前遍历的节点到根节点的路径值之和） - （存储在hash表中的值[即，此路径上若干个节点的路径和]），即所寻找到的路径+1；
     *  （4）同时，当此节点的左右子树皆已经被遍历完成的话，即，加上此节点后，所有可能的结果都已经被遍历，符合条件的情况皆已经被统计；
     *  即，当我们需要回到此遍历完成的节点的父节点时，需要将此节点到根节点的路径之和 从hash表中进行删除，
     *  ===> 由于此节点已被遍历完，所以其不太可能再次出现在另一条路径中
     */
    public int pathSum(TreeNode root, int targetSum) {
        // hash表，用来存储所遍历到的节点到根节点的路径 和 其出现的次数
        HashMap<Long, Integer> map = new HashMap<>();
        map.put(0L,1);
        return dfs(map , root , targetSum ,0L);
        // 所传递的参数：（1）hash表（hashmap）；（2）当前正在遍历的二叉树节点；（3）目标路径和；（4）当前路径和；
    }

    private int dfs(HashMap<Long, Integer> map, TreeNode root, int targetSum, long pathSum) {
        if(root == null){
            // 若是遍历到的二叉树节点不存在的话，即返回值count为0；
            return 0;
        }
        pathSum += root.val;
        // 获取pathSum（当前正在遍历的节点到根节点之间的距离之和） - targetSum（目标距离之和），
        // 若是其在hashmap表中出现过，即在减去其对应的路径，能够获取到对应的目标路径；
        int count = map.getOrDefault(pathSum - targetSum , 0);
        System.out.println(pathSum + "===>" + count);
        // 若是加上此正在遍历的节点值后的节点总值在hashmap中已经存在，即需要获取其在hashmap中的值（若是不存在的话，即为0） + 1
        map.put(pathSum , map.getOrDefault(pathSum , 0) + 1);

        count += dfs(map , root.left , targetSum , pathSum);
        count += dfs(map , root.right , targetSum , pathSum);

        // 当正在遍历的节点左右子树都已经被遍历完的话，即需要将其到根节点的路径之和，从统计当前路径所有可能值的hash表中进行删除
        map.put(pathSum , map.get(pathSum) - 1);
        return count;
    }
}
